package leetcode.l0615;

import java.util.Random;

/**
 * @author Retain
 * @date 2021/6/15 20:21
 */
public class Medium_分隔链表_86 {

    public static void main(String[] args) {
    }
    /**
     * 尝试的原地修改，理解错题意了，以为x是链表中的结点。。思路我觉得没问题，就是x是head的时候的操作没想出来应该怎么解决
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }
        // left指向最后一个比x小的元素，在它后面插入
        ListNode left = head;
        // right指向x结点
        ListNode right = head;
        ListNode xNode = null;
        while (right.val != x) {
            right = right.next;
        }
        while (left.val >= x) {
            left = left.next;
        }
        while (right != null) {
            xNode = right;
            // small:找到比x小的结点
            ListNode small = right.next;
            if (small != null && small.val < x) {
                // x结点指向下下个结点
                xNode.next = small.next;
                // small指向第一个比x大的结点
                small.next = left.next;
                // left指向sall
                left.next = small;
                // 移动 left
                left = small;
            }
            //没找到比x小的结点
            right = right.next;
        }
        return head;
    }

    /**
     * 哨兵结点，分成小链表和大链表，然后合并
     * @param head
     * @param x
     * @return
     */
    public ListNode partition2(ListNode head, int x) {
        ListNode small = new ListNode(0);
        ListNode smallHead = small;
        ListNode large = new ListNode(0);
        ListNode largeHead = large;
        while (head != null) {
            if (head.val < x) {
                small.next = head;
                small = small.next;
            } else {
                large.next = head;
                large = large.next;
            }
            head = head.next;
        }
        large.next = null;
        small.next = largeHead.next;
        return smallHead.next;
    }


     public static class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      }
}
